/*
 * Lab3.c
 *
 *  Created on: Aug 1, 2012
 *      Author: lakshmanas
 */

#include<stdio.h>

struct edge{
	int tail,head,color;
};

typedef struct edge edge_type;

edge_type *edges;
int *firstEdge;
int no_colors=0;
int *free_colors_a,*free_colors_b,*free_colors;
//colors assigned to vertex at a
int **colors_of_a;

//colors assigned to vertex at b
int **colors_of_b;

int **colors_of_a_b;

//no of vertexes m, n, and e edges in a bipartite graph
int m,n,e;
//a-b edge
int a=0,b=0;

FILE *file;

void find_ab_path(int a , int b, int color, int rightNode);
void get_free_colors_of_a(int node);
void get_free_colors_of_b(int node);
void get_free_colors_of_a_b(int a,int b);

int compreatailThenHead(const void* xin, const void* yin)
{
    int result;
    edge_type *x, *y;

    x = (edge_type*) xin;
    y = (edge_type*) yin;
    result = x->tail - y->tail;
    if (result != 0)
        return result;
    else
        return x->head - y->head;
}


void readInput(){

	int i=0,j=0;

	file =fopen("input1.dat","r");

	//printf("Enter no of vertexes m, n, and e edges in a bipartite graph \n");
	//scanf("%d %d %d",&m,&n,&e);
	fscanf(file,"%d %d %d",&m,&n,&e);
	//printf ("\n m=%d n=%d e=%d ",m,n,e);

/*
	if(m<n)
		no_colors=n;
	else
		no_colors=m;
*/

	//allocating memory for edges
	edges = (edge_type*) malloc(e*sizeof(edge_type));

	//printf("\nEdges for each of the m,n vertexes");
	for(i=0;i<e;i++){
        if (a < 0 || a >= n || b < 0 || b >= n) {
            printf("Invalid input %d %d at %d\n", a, b, __LINE__);
            exit(0);
        }
		//scanf("%d %d",&a,&b);
		fscanf(file,"%d %d",&a,&b);
		edges[i].tail=a;
		edges[i].head=b;
		edges[i].color=-1;
		if(a==0)
			no_colors++;
	}
	//printf("\n no of colors is %d",no_colors);

	qsort(edges,e,sizeof(edge_type),compreatailThenHead);
	// Coalesce duplicates into a single edge
	 j = 0;
	 for (i = 1; i < e; i++)
	 if (edges[j].tail == edges[i].tail && edges[j].head == edges[i].head)
	    ;
	 else {
	     	j++;
	     	edges[j].tail = edges[i].tail;
	     	edges[j].head = edges[i].head;
	       }
	    e = j + 1;

	 // For each vertex as a tail, determine first in range of edgeTab entries
	 firstEdge = (int*) malloc((n + 1) * sizeof(int));
	 if (!firstEdge) {
		 printf("malloc failed %d\n", __LINE__);
	        exit(0);
	    }
	 j = 0;
	 for (i = 0; i < n; i++) {
		 firstEdge[i] = j;
	     //printf("firstEdge[%d]=%d",i,j);
	     for (; j < e && edges[j].tail == i; j++)
	            ;
	    }
	  firstEdge[n] = e;


	  free_colors_a =(int*)malloc(no_colors*sizeof(int));
	  free_colors_b =(int*)malloc(no_colors*sizeof(int));
	  free_colors=(int*)malloc(no_colors*sizeof(int));

	  colors_of_a =(int **) malloc(m*sizeof(int*));
	  colors_of_b =(int **) malloc(n*sizeof(int*));
	  colors_of_a_b =(int **)malloc(m*sizeof(int*));

	  //assign -1 to all color edges starting from m
	for(i=0;i<m;i++){
	      colors_of_a[i]=(int *)malloc(no_colors*sizeof(int));
		for(j=0;j<no_colors;j++){
			colors_of_a[i][j]=-1;
			//printf("\n colors used by edges starting from a,%d is %d ",i,colors_of_a[i][j]);
		}
	}

	//assign -1 to all color edges starting from m
	for(i=0;i<n;i++){
		colors_of_b[i]=(int *)malloc(no_colors*sizeof(int));
		for(j=0;j<no_colors;j++){
			colors_of_b[i][j]=-1;
			//printf("\n colors used by edges starting from b,%d is %d ",i,colors_of_b[i][j]);
		}
	}

	for(i=0;i<m;i++){
		colors_of_a_b[i]=(int*)malloc(n*sizeof(int));
		for(j=0;j<n;j++){
			colors_of_a_b[i][j]=-1;
		}
	}
	  fclose(file);
}






//assign colors to each edge
void assignColor(){
	int i,j,k,l,color=-1,a=-1,b=-1;
	get_free_colors_of_a_b(0,0);
	//printf(" free colors at edge 0,0 ares ");
	for(i=0;i<no_colors;i++){
		//printf(" %d ",free_colors[i]);
	}

	for(i=0;i<e;i++){
		if(edges[i].color==-1){
			int tail= edges[i].tail;
			int head = edges[i].head;
			get_free_colors_of_a_b(tail,head);
			if(free_colors[0]!=-1){
/*
				printf("\n");
				for(l=0;l<no_colors;l++){
					printf("\t%d",free_colors[l]);
				}
*/
				color=free_colors[0];
				edges[i].color=color;
				colors_of_a_b[tail][head]=color;
				colors_of_a[tail][color]=1;
				colors_of_b[head][color]=1;
				printf("\n case 1: edge %d (%d %d) gets color %d",i,tail,head,color);
			}
			else{
				a=free_colors_a[0];
				b=free_colors_b[0];
				printf("\n case 2:  edge %d (%d %d) gets color ",i,tail,head);
				printf("a=%d, swaps with b=%d r:%d ",a,b,head);

				find_ab_path(a,b,a,head);
				colors_of_a_b[tail][head]=a;
				colors_of_a[tail][a]=1;
				colors_of_b[head][a]=1;
				colors_of_b[head][b]=1;
				//printf("\tcolors_of_a[%d][%d]=%d",tail,a,colors_of_a[tail][a]);
				//printf("\tcolors_of_b[%d][%d]=%d",head,a,colors_of_b[head][a]);

			}
		}
	}
}

// finds a-b path and alternates colors
void find_ab_path(int a , int b, int color, int rightNode){
	int i;
	if(color==a){
		for(i=0;i<m;i++){
			if(colors_of_a_b[i][rightNode]==color){
				printf(" l:%d ",i);
				find_ab_path(a,b,b,i);
				colors_of_a_b[i][rightNode]=b;
				//exchange a-b color
				if(!(colors_of_a[i][a]==1 && colors_of_a[i][b]==1)){
					colors_of_a[i][b]=1;
					colors_of_a[i][a]=-1;
				}

				//occupy new color
				//colors_of_a[i][b]=1;
				//colors_of_b[rightNode][b]=1;
				//free old color
				//colors_of_a[i][a]=-1;
				//colors_of_b[rightNode][a]=-1;
/*
				printf("\ncolors_of_a_b[%d][%d]=%d ",i,rightNode,b);
				printf("\tcolors_of_a[%d][%d]=%d ",i,b,colors_of_a[i][b]);
				printf("\tcolors_of_b[%d][%d]=%d ",rightNode,b,colors_of_b[rightNode][b]);
				printf("\t colors_of_a[%d][%d]=%d ",i,a,colors_of_a[i][a]);
				printf("\t colors_of_b[%d][%d]=%d ",rightNode,a,colors_of_b[rightNode][a]);
*/
				break;
			}
		}
	}
	else if(color==b){
		for(i=0;i<n;i++){
			if(colors_of_a_b[rightNode][i]==color){
				printf(" r:%d ",i);
				find_ab_path(a,b,a,i);
				colors_of_a_b[rightNode][i]=a;

				//exchange a-b color
				if(!(colors_of_b[i][a]==1 && colors_of_b[i][b]==1) ){
					colors_of_b[i][a]=1;
					colors_of_b[i][b]=-1;
				}

				//free old color
				//colors_of_a[rightNode][b]=-1;
				//colors_of_b[i][b]=-1;
/*
				printf("\ncolors_of_a_b[%d][%d]=%d ",rightNode,i,a);
				printf("\tcolors_of_a[%d][%d]=%d ",rightNode,a,colors_of_a[rightNode][a]);
				printf("\tcolors_of_b[%d][%d]=%d ",i,a,colors_of_b[i][a]);
				printf("\t colors_of_a[%d][%d]=%d ",rightNode,b,colors_of_a[rightNode][b]);
				printf("\t colors_of_b[%d][%d]=%d ",i,b,colors_of_b[i][b]);
*/
				break;
			}
		}
	}
}


/**
 * returns the list of available colors starting at node a
 */
void get_free_colors_of_a(int node){
	int i=0,j=0;
	//printf("\n available colors of a");
	for(j=0;j<no_colors;j++){
		//printf("%d ",colors_of_a[node][j]);
		free_colors_a[j]=-1;
	}
	//printf("\nfree_colors_a ");
	j=0;
	for(i=0;i<no_colors;i++){
		if(colors_of_a[node][i]==-1){
			free_colors_a[j]=i;
			//printf("%d ",i);
			//printf("\ncolors_of_a[%d][%d] =%d  free_color_a[%d]=%d;\t ",node,i,colors_of_a[node][i],j,free_colors_a[j]);
			j++;
		}
	}
}


/**
 * returns the list of available colors starting at node b
 */
void get_free_colors_of_b(int node){
	int i=0,j=0;
	//int free_color_b[no_colors];
	//printf("\n available colors of b");
	for(j=0;j<no_colors;j++){
		//printf("%d ",colors_of_b[node][j]);
		free_colors_b[j]=-1;
	}
	j=0;
	//printf("\nfree_colors_b ");
	for(i=0;i<no_colors;i++){
		if(colors_of_b[node][i]==-1){
			free_colors_b[j]=i;
			//printf("%d ",i);
			//printf("\ncolors_of_b[%d][%d] =%d  free_color_b[%d]=%d;\t ",node,i,colors_of_b[node][i],j,free_colors_b[j]);
			j++;
		}
	}
}


/**
 * returns the list of available colors for each edge a-b,
 * this method intersects the free colors of node and node b
 * and returns the list of free colors
 */
void get_free_colors_of_a_b(int a, int b){
	get_free_colors_of_a(a);
	get_free_colors_of_b(b);

	int i=0,j=0,k=0;

	for(i=0;i<no_colors;i++){
		free_colors[i]=-1;
	}
	i=0;j=0;k=0;
	while(i< no_colors && j< no_colors){
		//printf("%d %d",free_colors_a[i],free_colors_b[j]);
		if(free_colors_a[i]<free_colors_b[j])
			i++;
		else if(free_colors_b[j]<free_colors_a[i])
			j++;
		else {
			free_colors[k]=free_colors_a[i];
			k++;
			i++;
			j++;
		}
	}
}

void printEdge(){
	int i=0,j=0;
/*
	for(i=0;i<e;i++){
		printf("\n %d %d %d",edges[i].tail,edges[i].head,edges[i].color);
	}
*/
	for(i=0;i<m;i++){
		for(j=0;j<n;j++){
			if(colors_of_a_b[i][j]!=-1)
				printf("\n %d %d %d",i,j,colors_of_a_b[i][j]);
		}
	}
}

int main(){
	readInput();
	assignColor();
	printEdge();
}
